package main

/*
链表中的两数相加/两数相加_2(正序！ 正序！ 正序！)
给定两个 非空链表 l1和 l2 来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。
将这两数相加会返回一个新的链表。
可以假设除了数字 0 之外，这两个数字都不会以零开头。

示例1：
输入：l1 = [7,2,4,3], l2 = [5,6,4]
输出：[7,8,0,7]

示例2：
输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[8,0,7]

示例3：
输入：l1 = [0], l2 = [0]
输出：[0]
*/

type ListNode struct {
	Val  int
	Next *ListNode
}

//反转链表->相加->再反转
func addTwoNumbers1(l1 *ListNode, l2 *ListNode) *ListNode {
	rl1 := reverseList(l1)
	rl2 := reverseList(l2)

	carry := 0
	var pre *ListNode
	head := rl1

	for rl1 != nil && rl2 != nil {
		rl1.Val += carry + rl2.Val
		carry = rl1.Val / 10
		rl1.Val %= 10

		pre = rl1
		rl1 = rl1.Next
		rl2 = rl2.Next
	}
	if rl2 != nil {
		pre.Next = rl2
		rl1 = rl2
	}
	for rl1 != nil {
		rl1.Val += carry
		carry = rl1.Val / 10
		rl1.Val %= 10

		pre = rl1
		rl1 = rl1.Next
	}
	if carry > 0 {
		pre.Next = &ListNode{
			Val: carry,
		}
	}
	return reverseList(head)
}

func reverseList(head *ListNode) *ListNode {
	curr := head
	var pre *ListNode
	for curr != nil {
		next := curr.Next
		curr.Next = pre
		pre = curr
		curr = next
	}
	return pre
}

//使用栈 将两个链表末尾对其相加
func addTwoNumbers2(l1 *ListNode, l2 *ListNode) *ListNode {
	ptr1 := l1
	ptr2 := l2
	var stack1 []int
	var stack2 []int
	for ptr1 != nil {
		stack1 = append(stack1, ptr1.Val)
		ptr1 = ptr1.Next
	}
	for ptr2 != nil {
		stack2 = append(stack2, ptr2.Val)
		ptr2 = ptr2.Next
	}
	var c int
	var sum int
	n1 := len(stack1)
	n2 := len(stack2)
	if n1 < n2 {
		stack1, stack2 = stack2, stack1
		n1, n2 = n2, n1
	}
	var i int
	for ; i < n2; i++ {
		sum = stack1[n1-1-i] + stack2[n2-1-i] + c
		c = sum / 10
		sum %= 10
		stack1[n1-1-i] = sum
	}
	for ; i < n1; i++ {
		sum = stack1[n1-1-i] + c
		c = sum / 10
		sum %= 10
		stack1[n1-1-i] = sum
	}
	if c > 0 {
		stack1 = append([]int{c}, stack1...)
	}
	q := &ListNode{}
	cur := q
	n1 = len(stack1)
	for i := 0; i < n1; i++ {
		node := &ListNode{Val: stack1[i]}
		cur.Next = node
		cur = cur.Next
	}
	return q.Next
}

func main() {

}
